package org.everyday;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: Tang World
 * @Date: 3/9/2022 下午5:28
 */
public class L646 {
    public int findLongestChain(int[][] pairs) {
        // 本质上是最长递增子序列
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
        int[] dp = new int[pairs.length];
        int ans = 0;
        // base case
        Arrays.fill(dp, 1);

        for (int i = 1; i < dp.length; i++) {
            int preMax = 0;
            for (int j = 0; j < i; j++) {
                if (pairs[i][0] > pairs[j][1]) {
                    preMax = Math.max(preMax, dp[j]);
                }
            }
            dp[i] = preMax + 1;
            ans = Math.max(dp[i], ans);
        }
        return ans;
    }

    private int find2(int[][] pairs){
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
        List<Integer> arr = new ArrayList<Integer>();
        for (int[] p : pairs) {
            int x = p[0], y = p[1];
            if (arr.isEmpty() || x > arr.get(arr.size() - 1)) {
                arr.add(y);
            }else{
                // 小于x的y值所在的位置，更新该位置为新的y值（取原y和新y的最小值）
                int idx = binarySearch(arr, x);
                arr.set(idx, Math.min(arr.get(idx), y));
            }
        }
        return arr.size();
    }
    private int binarySearch(List<Integer> arr, int x) {
        int low = 0, high = arr.size() - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (arr.get(mid) >= x) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    public static void main(String[] args) {
        L646 l646 = new L646();
        l646.find2(new int[][]{{-9,8},{-6,9},{-6,-2},{-5,3},{-1,4},{0,3},{1,6},{8,10}});

    }
}
